Search results for "eksaktie kvantu algoritmi"

Eksakto kvantu vaicājošo algoritmu sarežģītība nejaušām Būla funkcijām

2018

Ir pierādīts, ka nejaušai n-bitu Būla funkcijai optimālam kvantu vaicājošajam algoritmam ir nepieciešami aptuveni n/2 vaicājumi, ja algoritmam ir atļauts kļūdīties ar nelielu varbūtību, taču eksaktajiem algoritmiem šī sarežģītība nav zināma. Šajā darbā tiek pētītas polinomiālās metodes iespējas eksaktas kvantu vaicājumu sarežģītības apakšējas robežas pierādīšanai. Tiek apskatīti tādi polinomi, kuru kvadrātu summa pārstāv doto Būla funkciju. Pirmkārt, ar pusnoteiktās programmēšanas palīdzību tiek skaitliski parādīts priekš n<=8, ka nejaušai n-bitu Būla funkcijai pietiekami precīzi |(n+1)/2| pakāpes polinomi eksistē ar lielu varbūtību. Otrkārt, tiek pierādīts, ka gandrīz visas Būla funkcijas …